Computer games and simulations, like most computer applications, have traditionally been limited to single play units (i.e. a single console which creates the display and is operated through one or several control devices or pads). The PC, because it can be networked via modems, on local network, or the internet, has opened up the possibility of games in which multiple player interact with each other.
Earlier work in this area describes one player connected to a single other player with simple modems. U.S. Pat. Nos. 5,292,125 and 5,350,176 to Hochstein and U.S. Pat. No. 5,538,255 to Barker describe computer game systems which can allow synchronized play between two players connect by a modem.
Later work, like U.S. Pat. Nos. 5,558,339, 5,896,444, and 5,956,485 to Perlman, describe small scale “client-server” models where a client came connects to a game server through a network. Because of game play models of this type being limited in the number of players which must be supported, most current PC games of this type allow a small number of players to interact, perhaps 10-30 players on a local area computer network. For small scale client-server games, the server can be simple and need not be optimized for the number of communication connections nor for quick/efficient access to game/client specific parameters.
Several newly release games, like Ultima Online and Everquest have expanded network player counts to the 1000-10,000 level. To achieve this level of multiple player interaction, these games use specialized central servers (or server clusters which are closely linked) which run programs that understand about all the players and how they interact with each other, thus, the individual player game systems are not complete without the central servers or server clusters. This technology has been described in the patent literature by U.S. Pat. No. 5,659,691 to Durward; U.S. Pat. No. 5,664,778 to Kikuchi and U.S. Pat. No. 5,668,950. U.S. Pat. No. 5,828,866 Hao et al. use the same concepts to distribute data in distributed CAD applications.
For the last several years, an alternative model for massive distributed play has been developed by elements of the U.S. Department of Defense and its contractors. This model is call “distributed simulation” because in its pure implementation, each client broadcasts its internal state changes (for instance object motions) to the network and reads all state changes from other clients to depict simulation changes which are computed on other client systems. Thus, no central server is needed to make the distributed system operate. The significant advantage of the distributed approach is that there is not a bottleneck at a central server (or server cluster), because each client can send data to another without going directly through a server.
The basics of this method of connecting applications into a network were refined from about 1985 to 1990 in a program generally name SIMNET. SIMNET technology was later renamed as DIS or Distributed Interactive Simulation. Some same publications from that period include Kraemer et al. (1987), Alluisi (1991), the DIS Steering Committee (1994), Calvin et al. (1995), Cosby (1995), Pullen et al. (1995) and later formal specifications documents from the IEEE (1278.1 and 1278.2 published in 1993 and 1995). Current Defense Department standards pertaining to distributed simulation, called the High Level Architecture or HLA, are published by the Defense Modeling and Simulation Office (1996).
In reality, some centralized functions still remain like finding all the players currently operating in the same distributed simulation space (so that the client can send and receive from them, the client needs to know their Internet or IP address). U.S. Pat. No. 5,685,775 to Bakoglu describes implementation of system like SIMNET but for operation via standard dial-up phone networking (SIMNET, DIS, and HLA have always assumed Internet LAN/WAN network architectures for higher state exchange rates). U.S. Pat. No. 5,775,996 to Othmer and U.S. Pat. No. 5,956,485 to Perlman describe brokering mechanisms which were similar to those integral to SINET systems as early as 1989. U.S. Pat. No. 5,899,810 to Smith and U.S. Pat. No. 6,006,254 to Waters et al. are examples of commercially targeted systems which were influenced by the DIS and HLA architecture.
Similarly, it may be advantageous to access certain centralized databases and files (like common descriptions of play area virtual terrain). These centralized functions, however, are characterized as being needed when a new client joins the simulations and when it leaves it. Thus, the more limited server is usually called a simulation broker, and can actually be implemented as part of the first client which initiates new simulated space. Centralized database distributions are described in U.S. Pat. No. 5,659,691 to Durward; U.S. Pat. No. 5,984,786 to Ehrrman; and U.S. Pat. No. 6,006,254 to Waters et al., but none of these focus only on data needed only for joining, and rather, in the spirit of client-server multiplay, provide databases from centralized points which interact intimately with on-going game playing.
For simulations like those performed in military training, over relatively high-speed networks, this advantage can be realized. However, if the simulation client is operating through a lower performance link like a dial-up modern, replicating packets to all other clients in a large pool (potentially including 1000+ clients) is not practical (i.e. the speed of transmission over the slow link precludes sending to many clients at once). This problem at the client communication end has motivate most of the client-server type solutions referenced (Hochstein U.S. Pat. No. 5,292,125 and U.S. Pat. No. 5,350,176, Barker U.S. Pat. No. 5,538,255—only two players at a time; Perlman U.S. Pat. Nos. 5,558,339, 5,896,444, 5,956,485, Durward et al. U.S. Pat. No. 5,659,691, Kikuchi et al. U.S. Pat. Nos. 5,664,778, 5,668,950, Bakoglu et al. U.S. Pat. No. 5,685,775, Barrus U.S. Pat. No. 5,736,990—small numbers of players over bandwidth limited networks; Smith U.S. Pat. No. 5,899,810, Ehrman U.S. Pat. No. 5,984,786, Water et al. U.S. Pat. No. 6,006,254, Vange et al. U.S. Pat. No. 6,050,098, Kappler U.S. Pat. No. 6,064,677—combination of distributed, client-server, and message priority queuing to improve performance in the network and on the central server). Work to overcome aspects of the problems which arise because of poor server or network performance are described by Barrus et. al. U.S. Pat. No. 5,736,990, Othmer et al. U.S. Pat. No. 5,775,996, O'Callaghan U.S. Pat. No. 5,820,463, Waters U.S. Pat. No. 5,920,862, Lambright et al. U.S. Pat. No. 6,015,348, Vange et al. U.S. Pat. No. 6,050,098, and Kappler U.S. Pat. No. 6,064,677.
One solution to this problem is inserting a repeater router, which reads packets from each client and resends them to all relevant other clients which need to see the particular state change. In a simple form this has already been defined for the Internet using a concept called multicast. In multicast, a source client and all of its destination peers establish a multicast connection so that when the client sends its packet once into the Internet, properly featured Internet routers (which are really in this case servers with repeater routers) replicate that packet and route it to all destination clients without the source client sending the data out multiple times.
Some replication methods used in multicast have described by Chen et al. U.S. Pat. No. 5,666,360 and in numerous Internet published Request For Comment (RFC—these publicly distributed papers describe all interoperability standards used to implement the modem Internet and its protocols for data exchange; RFC are solicited and published by the Internet Society). Some RFC and papers defining details of Internet Protocol (IP) based multicasting are defined in Deering, RFC 1112, Pullen et al. (1995), Armitage RFC 2022 and RFC 2191, Fenner RFC 1112, Talpade et al. RFC 2149, and Pullen et al. RFC 2502 and RFC 2490.
Multicast, as built into some Internet routers and backbones, is conceptually very simple. One packet from a source goes in and multiple packets to multiple clients go out (more or less by copying or replicating the input packet). The service as currently designed has been built for replication data from one point in to many out to deliver media like digital video or digital audio (the digital Internet equivalent to broadcast TV or radio). For this type of use, there is no way to reduce replication effort through knowledge of the data being sent—if a client is “tuned” to a digital TV station, it needs copies of the packets being sent from that station (or packet source).
Some of the RFC disclosed applications specific streaming protocols for audio, video, and other data are defined in Schulzrinne, “RTP Profile for Audio and Video Conferences with Minimal Control,” RFC 1890; Schulzrinne et al., “RTP: A Transport Protocol for Real-Time Applications,” RFC 1889 and Real Time Streaming Protocol (RTSP), “RFC 2326; Defense Modeling and Simulation Office, High Level Architecture Riles Version 1.0; Handley et al., “SDP: Session Description Protocol,” RFC 2327, and Arango et al., “Media Gateway Control Protocol (MGCP) Version 1.0,” RFC 2706.
In Pullen et al., “A Simulation Model for IP Multicast with RSVP,” RFC 2490, the authors point out a number of deficiencies in using current IP multicast to service distributed simulation. These center around the difficulty in allowing a specific simulation client into and out of multicast groups (i.e. groups which will need the clients state broadcast packets) quickly (presumably due to some application culling rule changes as a client simulation executes). This presumes that making and breaking multicast group membership is the best way to optimize packet flows.
However, rather than making multicast more efficient (which is certainly a good idea, especially for applications independent uses) in distributed simulation and gaming, an alternative of making the routing system more intelligent about what and where data is needed can also have a significant impact on overall group or federation performance. Consider that quite a bit of knowledge is available about the source and destination clients and the objects being simulated or displayed on these clients. For instance, if the object on a client station which represent client avatar (or player self) in the game is in one place, it will not be able to see another object being simulated by another client if that object is (1) behind a wall, (2) too far away, (3) moving too quickly, (4) obscured by smoke or weather, to name a few simple culling rules.
Similarly, since each object is a depiction of something with acceleration and mass properties, it cannot change is location, velocity, or acceleration outside of some operating envelope. This means that each client can track objects and predict within some error bound where they will be at each point in the future. If the predicted value is close enough to the value from the client where the object is being created (and probably controlled by a player), its state changes need not be sent to other clients which can used the predicted location. Updates are only required when predictions are different from actual location by a large enough amount to effect the quality of play.
Culling rules based on proximity in the network [Seaman U.S. Pat. No. 5,644,571], proximity in virtual space [Barrus et al. U.S. Pat. No. 5,736,990], [Waters et al. U.S. Pat. No. 5,841,980], [Waters U.S. Pat. No. 5,920,862], and [Lambright et al. U.S. Pat. No. 6,015,348], and priority [Vange et al. U.S. Pat. No. 6,050,098] and [Kappler et al. U.S. Pat. No. 6,064,677] have been used in client-server systems. However, these concepts have not been extended into IP multicast or conventional routers.
The advantages of putting application-specific information actually into the routing system are many. Backbone routers provide the highest level of access to the Internet. Thus, routing data from lower echelon networks (and client-point-to-router connections) into an upper echelon router, which in turn, determines routing quality of service based on the needs of the federation (i.e. the needs based on source and destination state data which is available to the router because of the record of past packet traffic through it), can substantially reduce overall traffic over the backbone. Since network traffic is directly translatable to cost and performance, utilizing application (game) specific data routing performance and packet traffic reduction rules reduces cost and while improving multiplay game play performance. Culling rules inserted into the router is a specific instance of the concept of inserting portable applications or applets into the route. This is analogous to adding special purposed functionality to a general purpose web by adding applets (which might be downloaded into it).